package imooc_math.sort;
/* 用数组存储二叉堆，下标从0开始存储时：
 * 子结点分别是父节点的(2x+1)与(2x+2)
 * 父节点=(子节点-1)/2
 * 最后一个非叶子节点的索引=(count-1)/2--（数组最大下标（即length-1）-1）/2
 * */
public class HeapSort {
	private static int count;
	public static void sort(Comparable[] arr){
		count=arr.length;
		for(int i=arr.length-1;i>0;i--){
			swap(arr,0,i);
			shiftDown(arr,0);
		}
	}
	  public static void shiftDown(Comparable[] arr,int k){
	    	while(2*k+1<=count){
	    		int j=2*k+1;
	    		if(j+1<=count&&arr[j+1].compareTo(arr[j])>0){
	    			j=j+1;
	    		}
	    		if(arr[k].compareTo(arr[j])>=0){
	    			break;
	    		}
	    		swap(arr,j,k);
	    		k=j;
	    	}

	    }
	public static void swap(Object [] arr,int a,int b){
		Object t=arr[a];
		arr[a]=arr[b];
		arr[b]=t;
	}
}
